package linkedlist.josephus;

/**
 * @author : Rookie
 * @description : 循环链表解决约瑟夫环
 * @date : 2023/6/6
 */
public class CyclicListMethod {

    static class LinkNode {
        int val;
        LinkNode next;

        public LinkNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    /**
     * 约瑟夫环问题解决
     * @param n 总人数
     * @param m 第几个出列
     */
    public static void josephus(int n,int m) {

        StringBuilder sb = new StringBuilder();

        LinkNode head = new LinkNode(1);
        LinkNode currNode = head;
        for (int i = 2; i <= n ; i++) {
            currNode.next = new LinkNode(i);
            currNode = currNode.next;
        }
        // 链表尾指向头 形成循环链表
        currNode.next = head;

        // 记录当前节点
        LinkNode curr = head;
        // 记录当前节点的前一个节点
        LinkNode prev = head;

        // 满足curr.next=curr时 链表中只有一个元素
        while (curr.next != curr) {
            int count = 1;
            // 当 ptr1 指向要被删除的节点时，我们将 ptr2 的 next 指向它的下一个节点，并将 ptr1 指向 ptr2 的下一个节点以便继续遍历。
            while (count != m) {
                prev = curr;
                curr = curr.next;
                count ++;
            }
            sb.append(curr.val).append(" ");
            // 删除curr节点
            prev.next = curr.next;
            // 当前节点为prev节点下一节点 即为curr.next
            curr = prev.next;
        }
        sb.append(curr.val);
        System.out.println("出列顺序： " + sb);
    }

    public static void main(String[] args) {
        josephus(20,5);
    }
}
